using System;

namespace getPrimeFactor
{
	/// <summary>
	/// GetPrimeFactor の概要の説明です。
	/// </summary>
	class GetPrimeFactor
	{
		/// <summary>
		/// アプリケーションのメイン エントリ ポイントです。
		/// </summary>
		[STAThread]
		static void Main(string[] args)
		{
			long lNumberToCalc;		//計算しようとする数字
			long lTempNumber;		//一時計算用数字
			long lMinPrimeFactor;	//一時計算用数字の最小質因子

			string sInput;
			System.Text.StringBuilder sbResult;

			//ソフトウェア説明
			Console.WriteLine("Get all Prime Factors of the entered number.");
			Console.Write("Min:2 Max:");
			Console.WriteLine(long.MaxValue.ToString());
			Console.WriteLine("'e' for Exit.");
			Console.WriteLine("");

			for(;;)	//Loop
			{
				sbResult = new System.Text.StringBuilder();

				Console.Write("Input the number:");
				sInput = Console.ReadLine();

				//"e"の場合はExit
				if(sInput == "e") break;

				if(sInput == "") continue;

				try
				{
					//入力値をlongに変換
					lNumberToCalc = long.Parse(sInput);
				}
				catch
				{
					//変換エラー → 入力不正
					Console.WriteLine("Input Error!");
					continue;
				}

				if(lNumberToCalc < 2)
				{
					Console.WriteLine("Input Error!");
					continue;
				}

				//入力値を一時計算用数字にセット
				lTempNumber = lNumberToCalc;

				//質因子を取得
				for(;;)
				{
					//一時計算用数字の最小質因子を取得
					lMinPrimeFactor = getMinPrimeFactor(lTempNumber);

					if(lMinPrimeFactor == 1)	//最小質因子が1 → 一時計算用数字は質数
					{
						if(lTempNumber == lNumberToCalc)	//一時計算用数字は入力値 → 入力値は質数
						{
							sbResult.Append("A prime number.");
						}
						else	//一時計算用数字は入力値じゃない → 入力値の最大質因子
						{
							sbResult.Append(lTempNumber.ToString());
							sbResult.Append(",");
						}

						//計算終了
						break;
					}
					else	//最小質因子が1じゃない → 一時計算用数字の最小質因子
					{
						sbResult.Append(lMinPrimeFactor.ToString());
						sbResult.Append(",");

						//一時計算用数字から最小質因子を除いて、次の一時計算用数字を生成して、計算を続く
						lTempNumber = lTempNumber / lMinPrimeFactor;
					}
				}

				//最後のカンマを消す
				sbResult.Remove(sbResult.Length-1, 1);

				//結果を表示
				Console.WriteLine(sbResult.ToString());
			}
		}

		//最小質因子を取得
		private static long getMinPrimeFactor(long lTempNumber)
		{
			//2は質数
			if(lTempNumber == 2) return 1;

			long i;
			long lEnd;
			bool flag = false;

			//lTempNumberまで計算しなくても、その平方根以下の一番大きい整数まででいい
			lEnd = (long)System.Math.Floor(System.Math.Sqrt(lTempNumber));

			for(i = 2; i <= lEnd; i++ )
			{
				//2から1つずつ整除チェック
				if( (lTempNumber % i) == 0)
				{
					//整除なら、最小質因子取得
					flag = true;
					break;
				}
			}

			if(flag == false) i = 1;

			return i;
		}

	}
}
